package com.haidechizi.leetcode;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author: wangdejun
 * @create: 2020-04-17 12:10
 **/
public class _1202_交换字符串中的元素 {

    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (List<Integer> list : pairs) {
            List<Integer> integers = map.getOrDefault(list.get(0), new ArrayList<Integer>());
            integers.add(list.get(1));
            map.put(list.get(0), integers);
        }

        boolean flag = true;
        char[] chars = s.toCharArray();
        while (flag) {
            flag = false;
            for (int i = 0; i < chars.length; i++) {
                List<Integer> list = map.get(i);
                if (list == null || list.size() == 0) {
                    continue;
                }
                for (int value : list) {
                    if (chars[i] > chars[value]) {
                        swap(chars, i, value);
                        flag = true;
                    }
                }
            }
        }
        return String.valueOf(chars);
    }

    public void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}
